package basic.study.wantOffer.chapter5;

import java.util.Arrays;

/**
 * @ClassName Problem48
 * @Description  最长不含重复字符的子字符串
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/5 13:50
 * @Version 1.0
 */
public class Problem48 {
    class LongestSubstringWithoutDup {
        public int  maxLength(String str) {
            int[] pos = new int[26];
            Arrays.fill(pos, -1);
            char[] chars = str.toCharArray();

            int pre = 0;
            int cur = 0;
            int maxLen = 0;

            for (int i = 0; i < chars.length; i++) {
                int idx = chars[i] - 'a';
                if (pos[idx] == -1) {//如果没有这个数
                    cur = pre + 1;
                } else {
                    int d = i - pos[idx];
                    if (d > pre) {
                        cur = pre + 1;
                    } else {// d <= pre
                        cur = d;
                    }
                }
                pos[idx] = i;
                pre = cur;
                if (cur > maxLen) {
                    maxLen = cur;
                }
            }
            return maxLen;
        }
    }
}
